home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / rb_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.2 KB  |  275 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  rb_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef RBTREEH
  19. #define RBTREEH
  20.  
  21. //------------------------------------------------------------------------------
  22. //
  23. // rb_tree:  red black trees (leaf oriented)
  24. //
  25. // Walter Zimmer      (1989)
  26. //
  27. // Implementation as described in
  28. // Kurt Mehlhorn : "Data Structures and Algorithms 1", section III.5.2
  29. //
  30. // Modifications:
  31. // - Virtual compare function                         (S. Naeher, Aug. 1989)
  32. // - Delete: overwrite copies of keys in inner nodes  (S. Naeher, Okt. 1989)
  33. // 
  34. //------------------------------------------------------------------------------
  35.  
  36. #include <LEDA/basic.h>
  37. #include <LEDA/b_stack.h>
  38.  
  39.  
  40. // falls TEST def. ist => tracen der aufgerufenen fkt.
  41. // falls TEST1 def. ist => test auf schwarztiefe und print moegl. 
  42.  
  43. #define NOTEST
  44. #define TEST1
  45.  
  46. #ifdef TEST
  47. #define TRACE(x)  cout << form x
  48. #define TRACE2(x,ebene)  if ( debug >= (ebene) ) cout << form  x
  49. #define TRACE_FUNC(x) x
  50. // extern int debug ;  muss im testprogramm definiert werden falls
  51. // TRACE2(x,ebene) benutzt wird
  52. #else 
  53. #define TRACE(x) 
  54. #define TRACE2(x,ebene) 
  55. #define TRACE_FUNC(x) 
  56. #endif
  57.  
  58.  
  59. //--------------------------------------------------------------------
  60. // some declarations and type definitions
  61. //--------------------------------------------------------------------
  62.  
  63. class rb_tree;
  64. class rb_tree_node;
  65.  
  66. typedef rb_tree_node* rb_tree_node_ptr;
  67.  
  68. typedef rb_tree_node* rb_tree_item;
  69.  
  70. typedef rb_tree_node* (*get_node_fct)(ent);
  71.  
  72.  
  73. typedef void (*DRAW_RB_NODE_FCT)(double,double,void*);
  74. typedef void (*DRAW_RB_EDGE_FCT)(double,double,double,double);
  75.  
  76. struct stack_el {
  77.   rb_tree_node* nodeptr;
  78.  
  79.   int dir;   /* 0: left
  80.                 1: right
  81.                 2: undefined
  82.              */
  83.  
  84.   stack_el (rb_tree_node* p,int d)
  85.      { nodeptr = p; dir = d ; }
  86.   stack_el ()
  87.      { nodeptr = 0; dir = 2; }
  88. };
  89.  
  90. typedef stack_el* stack_el_ptr;
  91. declare(b_stack,stack_el);
  92. typedef b_stack(stack_el)  rb_tree_stack;
  93.  
  94. // ----------------------------------------------------------------
  95. // class rb_tree_node 
  96. // ----------------------------------------------------------------
  97.  
  98. class rb_tree_node
  99. {  ent e;                  // entry
  100.    ent k;                  // searchkey
  101.  
  102.    int c;                  // color
  103.                            // for leaves red =2 , black = 3
  104.                            // for nodes  red =0 , black = 1
  105.                            // 4: unknown
  106.  
  107.    rb_tree_node* son[2];   // left and right son
  108.  
  109.    friend class rb_tree;
  110.  
  111.    public :
  112.  
  113.    ent entry()   { return e; }
  114.    ent key()     { return k; }
  115.    int col()  { return c; }
  116.  
  117.    // fuer blatter ist red =2 , black = 3
  118.    // fuer knoten  ist red =0 , black = 1
  119.  
  120.    int is_node()   { return  col() <  2; } 
  121.    int is_leaf()   { return  col() <  2; }
  122.    int is_black()  { return  col() &  1; }   
  123.    int is_red()    { return  !is_black();}   
  124.  
  125.    void gets_red_node()   { c = 0; }
  126.    void gets_black_node() { c = 1; }
  127.    void gets_red_leaf()   { c = 2; }
  128.    void gets_black_leaf() { c = 3; }
  129.  
  130.    rb_tree_node(ent K = 0 , ent E = 0 ,  int color = 4  ,                            rb_tree_node* leftson = 0 , rb_tree_node* rightson = 0)
  131.    {  
  132.       k = K ;
  133.       e = E ; 
  134.       c = color ;
  135.       son[0] = leftson ;
  136.       son[1] = rightson;
  137.    }         
  138.  
  139.    rb_tree_node(rb_tree_node_ptr p)
  140.    {
  141.       k = p->key();
  142.       e = p->entry() ;
  143.       c = p->col();
  144.       son[0] = 0;
  145.       son[1] = 0;
  146.    }         
  147.  
  148.    OPERATOR_NEW(5)
  149.    OPERATOR_DEL(5)
  150.  
  151. };
  152.  
  153.  
  154. // ----------------------------------------------------------------
  155. // class rb_tree
  156. // ----------------------------------------------------------------
  157.  
  158. class rb_tree
  159. { 
  160.   rb_tree_node* root;
  161.   rb_tree_node* list_ptr;   // zeigt auf des minimum im baum
  162.   int counter;             // auf Vax genuegt int , sonst vielleicht long noetig
  163.   rb_tree_stack st;
  164.  
  165.  
  166.   rb_tree_node* get_node1(ent)   const;
  167.   rb_tree_node* get_node(ent x)  const{ return get_node1(x) ; } 
  168.   rb_tree_node* search(ent);
  169.  
  170.   rb_tree_node* copy_tree(rb_tree_node*,rb_tree_node_ptr&) const;
  171.  
  172.   void del_tree(rb_tree_node*);
  173.  
  174.   void pop(rb_tree_node_ptr& q,int& dir);
  175.  
  176.   void push(rb_tree_node_ptr q,int dir1)
  177.     { stack_el z(q,dir1) ; st.push(z) ; }
  178.  
  179.   void rotation(rb_tree_node*,rb_tree_node*,int);
  180.   void double_rotation(rb_tree_node*,rb_tree_node*,rb_tree_node*,int,int);
  181.   void if_root(rb_tree_node*,rb_tree_node*);
  182.  
  183.  
  184.   virtual int cmp(ent& x,ent& y) const { return int(x)-int(y); }
  185.  
  186.   virtual void clear_key(ent& x) const { Clear(x); }
  187.   virtual void clear_inf(ent& x) const { Clear(x); }
  188.  
  189.   virtual void copy_key(ent& x)  const { Copy(x);  }
  190.   virtual void copy_inf(ent& x)  const { Copy(x);  }
  191.  
  192.   public:
  193.  
  194.   rb_tree_node* first_item()             const  { return list_ptr; }
  195.   rb_tree_node* next_item(rb_tree_node*) const;
  196.  
  197.   rb_tree_node* next_smaller(ent) const;
  198.   rb_tree_node* next_bigger(ent)  const;
  199.  
  200.   rb_tree_node* succ(rb_tree_node* p) const
  201.   {return ( !p  ||  p->son[1] == list_ptr ) ? 0 : p->son[1]; }
  202.  
  203.   rb_tree_node* pred(rb_tree_node* p) const
  204.   { return ( !p  ||  p == list_ptr   )  ?  0 : p->son[0] ; }
  205.  
  206.   rb_tree_node* cyclic_succ(rb_tree_node* p) const
  207.   { return p ? p->son[1] : 0; }
  208.  
  209.   rb_tree_node* cyclic_pred(rb_tree_node* p) const
  210.   { return p ? p->son[0] : 0; }
  211.  
  212.   rb_tree_node* min() const { return list_ptr; }
  213.   rb_tree_node* find_min() const { return list_ptr; }
  214.   rb_tree_node* max() const { return ( list_ptr ? list_ptr->son[0] : 0  ) ; }
  215.  
  216.   void del_min()                { if (root)  del(min()->k); }
  217.   void del_item(rb_tree_node* p){ if (p)     del(p->k); }
  218.   void del_max()                { if (root)  del(max()->k); }
  219.  
  220.   void decrease_key(rb_tree_node* p, ent k) { ent i = p->e; 
  221.                                               copy_inf(i);
  222.                                               del(p->k); 
  223.                                               insert(k,i);
  224.                                               clear_inf(i);
  225.                                              }
  226.  
  227.   void del(ent);
  228.  
  229.   rb_tree_node* insert(ent,ent);
  230.   rb_tree_node* lookup(ent) const;
  231.   int  member(ent)          const;
  232.  
  233.   ent& access(ent);
  234.   void change_inf(rb_tree_node*,ent);
  235.  
  236.   ent   key(rb_tree_node* p)  const { return  p->key() ;  }
  237.   ent&  info(rb_tree_node* p) const { return  p->e ;      }
  238.   ent   inf(rb_tree_node* p)  const { return  p->e ;      }
  239.  
  240.   int size()   const { return counter; } 
  241.   int empty()  const { return root ? false : true ; }
  242.   void clear();
  243.  
  244.  
  245.   rb_tree()  : st(32)
  246.   {  root  = list_ptr = 0 ;
  247.      counter = 0; 
  248.   }
  249.  
  250.   rb_tree(const rb_tree&);
  251.   rb_tree& operator=(const rb_tree&);
  252.  
  253.   ~rb_tree() { clear(); }
  254.  
  255.  
  256.   void draw(DRAW_RB_NODE_FCT, DRAW_RB_NODE_FCT, DRAW_RB_EDGE_FCT, rb_tree_node*,
  257.           double, double, double, double, double);
  258.  
  259.   void draw(DRAW_RB_NODE_FCT, DRAW_RB_NODE_FCT, DRAW_RB_EDGE_FCT, 
  260.           double, double, double, double);
  261.  
  262. #ifdef TEST1
  263.  
  264.   int black_deep_test() const;
  265.   int deep_test(rb_tree_node*) const;
  266.  
  267.   void print() const;
  268.   void print_tree(rb_tree_node*,int) const;
  269.  
  270. #endif
  271.  
  272. };
  273.  
  274. #endif  #RBTREEH
  275.